/**
 * The first two cyclic numbers are 142857 and 0588235294117647.
 *
 * There is only one cyclic number for which, the eleven leftmost digits
 * are 00000000137 and the five rightmost digits are 56789 (i.e., it has
 * the form 00000000137...56789 with an unknown number of digits in the
 * middle). Find the sum of all its digits.
 */

#include <iostream>
#include "euler/prime_factor.hpp"
#include "euler/prime_test.hpp"
#include "euler/modular.hpp"
#include "euler.h"

BEGIN_PROBLEM(358, solve_problem_358)
	PROBLEM_TITLE("Cyclic numbers")
	PROBLEM_ANSWER("3284144505")
	PROBLEM_DIFFICULTY(2)
	PROBLEM_FUN_LEVEL(1)
	PROBLEM_TIME_COMPLEXITY("m*n*log(n)")
	PROBLEM_SPACE_COMPLEXITY("log(n)")
END_PROBLEM()

// Tests whether a prime p is full-reptend. This is equivalent to
// testing if any of (p-1)'s divisors, k, satisfies 10^k = 1 (mod p).
static bool is_full_reptend_prime(int p)
{
	bool found = false;
	euler::prime_factorize_distinct(p - 1, [p,&found](int n, int /* k */) {
		int a = (p - 1) / n;
		if (euler::modpow(10, a, p) == 1)
			found = true;
	});
	return !found;
}

static void solve_problem_358()
{
	bool verbose = false;
	for (int p = 724709891; p <= 729909891; p += 100000)
	{
		if (euler::is_prime(p))
		{
			bool b = is_full_reptend_prime(p);
			if (verbose)
			{
				std::cout << p << " is a full reptend prime: "
					<< std::boolalpha << b << std::endl;
			}
			if (b)
				std::cout << 9LL*(p-1)/2 << std::endl;
		}
	}
}
